package LearnAlgorithm.f_字符串;

import java.util.Arrays;
import java.util.HashMap;

/*
变形词:两个串有相同的字符及数量组成abc abc , abc cba, gabcd bcadq;
给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另1个字符串
这里规定大小写为不同字符，且考虑字符串中的空格
给定一个stringA和一个stringB,请返回一个boolean,代表两串是否重新排列后可相同
保证两串的长度都小于等于5000
测试样例:
"Here you are", "Are you here"
返回:
false
*/
public class c判断两串构成变形词 {
	public static void main(String[] args) {
		String aString = "abcdd";
		String bString = "dcbac";
//		System.out.println(checkSame(aString, bString));
//		System.out.println(checkSameUseMySort(aString, bString));
		System.out.println(checkSameByAscll(aString, bString));
	}
	
	/**
	 * O(N)
	 * @param aString
	 * @param bString
	 * @return
	 */
	public static boolean checkSameByAscll(String aString, String bString) {
		int[] ascllArr = new int[128];
		for (int i = 0; i < aString.length(); i++) {
			ascllArr[(int) aString.charAt(i)]++;
		}
		for (int i = 0; i < bString.length(); i++) {
			ascllArr[(int) bString.charAt(i)]--;
			if (ascllArr[(int) bString.charAt(i)] < 0) {
				return false;
			}
		}
		for (int i = 0; i < ascllArr.length; i++) {
			if (ascllArr[i] > 0) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * O(NlogN)
	 * @param aString
	 * @param bString
	 * @return
	 */
	public static boolean checkSameUseMySort(String aString, String bString) {
		int aLen = aString.length();
		int bLen = bString.length();
		if (aLen != bLen) {
			return false;
		}
		char[] aCharArr = aString.toCharArray();
		char[] bCharArr = bString.toCharArray();
		quickSortThree(aCharArr, 0, aLen - 1);
		quickSortThree(bCharArr, 0, bLen - 1);
		return Arrays.equals(aCharArr, bCharArr);//若两个数组的长度相等，且每一个位置的元素也相等，则认为这两个数组相等
	}
	
	/**
	 * O(NlogN)
	 * @param aString
	 * @param bString
	 * @return
	 */
	public static boolean checkSame(String aString, String bString) {
		int aLen = aString.length();
		int bLen = bString.length();
		if (aLen != bLen) {
			return false;
		}
		char[] aCharArr = aString.toCharArray();
		char[] bCharArr = bString.toCharArray();
		Arrays.sort(aCharArr);
		Arrays.sort(bCharArr);
		return Arrays.equals(aCharArr, bCharArr);//若两个数组的长度相等，且每一个位置的元素也相等，则认为这两个数组相等
	}
	
	public static void quickSortThree(char[] arr, int p, int r) {
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int[] q = partitionThree(arr, p, r);
				quickSortThree(arr, p, q[0] - 1);
				quickSortThree(arr, q[1] + 1, r);
			}
		}
	}
	
	public static int[] partitionThree(char[] arr, int p, int r) {
		int equalLast = p + 1;
		int beginer = p + 1;
		int bigger = r;
		int midIndex = getMedian(arr, p, r);
		swap(arr, p, midIndex);
		int piovet = arr[p];
		int[] equalNumber = new int[2];
		while (beginer <= bigger) {
			while (beginer <= bigger && arr[beginer] <= piovet) {
				if (arr[beginer] < piovet && equalLast == beginer) {
					beginer++;
					equalLast++;
				} else if (arr[beginer] < piovet && beginer != equalLast) {
					swap(arr, beginer, equalLast);
					beginer++;
					equalLast++;
				} else {
					beginer++;
				}
			}
			while (beginer <= bigger && arr[bigger] > piovet) {
				bigger--;
			}
			if (beginer < bigger) {
				swap(arr, beginer, bigger);
			}
		}
		swap(arr, p, bigger);
		equalNumber[0] = equalLast - 1;
		equalNumber[1] = bigger;
		return equalNumber;
	}
	
	public static int getMedian(char[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1);
		int indexOfMedians = 0;
		char[] medians = new char[groupSize];
		HashMap<Character, Integer> mediansOfValueAndIndex = new HashMap<Character, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + i * 5, r);
				medians[indexOfMedians++] = arr[(p + i * 5 + r) >>> 1];
				mediansOfValueAndIndex.put(arr[(p + i * 5 + r) >>> 1], (p + i * 5 + r) >>> 1);
			} else {
				insertSort(arr, p + i * 5, p + i * 5 + 4);
				medians[indexOfMedians++] = arr[p + i * 5 + 2];
				mediansOfValueAndIndex.put(arr[p + i * 5 + 2], p + i * 5 + 2);
			}
		}
		insertSort(medians, 0, groupSize - 1);
		return mediansOfValueAndIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public static void insertSort(char[] arr, int p, int r) {
		int before_i = 0;
		char value_i;
		for (int i = p + 1; i <= r; i++) {
			before_i = i - 1;
			value_i = arr[i];
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i--];
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	public static void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
